Silvio Micali
Abstract:
In an auction, a player may not exactly know his own valuation, nor its distribution. We thus study single-good auctions whose players know their own valuations only within a multiplicative factor (e.g., 10%). The notions of implementation in dominant and undominated strategies are naturally extended to this setting, but their power is vastly different. Namely,
(1) We prove that no dominant-strategy mechanism can guarantee more social welfare than by assigning the good at random; but
(2) We prove a much better performance can be obtained via undominated-strategy mechanisms, and actually provide tight upper and lower bounds for the fraction of the maximum social welfare guaranteable by such mechanisms, whether deterministic or probabilistic.
Join work with Alessandro Chiesa and Zeyuan Zhu